package com.wwz.leetcode;


import java.util.*;

public class LeetCode1640 {
    public static void main(String[] args) {
        int arr[] = {1, 2, 3};
        int pieces[][] = {{2}, {1, 3}};
        System.out.println(canFormArray(arr, pieces));
    }

    public static boolean array(int arr[], int pieces[][]) {
        int length = pieces.length;
        int count = 0;
        for (int[] piece : pieces) {
            if (piece.length > 1) {
                int temp = 0;
                TreeMap treeMap = new TreeMap();
                for (int i = 0; i < arr.length; i++) {
                    for (int i1 : piece) {
                        if (arr[i] == i1) {
                            temp++;
                            int index = getIndex(arr[i], arr);
                            if (treeMap.size() > 0 && Integer.parseInt(treeMap.lastKey().toString()) + 1 != index) {
                                return false;
                            }
                            treeMap.put(index, arr[i]);
                        }
                    }
                    if (temp == piece.length) {
                        Iterator<String> it = treeMap.keySet().iterator();
                        int n = 0, m = 0;
                        while (it.hasNext()) {
                            if (piece[n] == Integer.parseInt(treeMap.get(it.next()).toString())) {
                                m++;
                            }
                            n++;
                        }
                        if (m == piece.length) {
                            count++;
                            treeMap.clear();
                        }
                    }
                }

            } else {
                for (int i : arr) {
                    if (piece[0] == i) {
                        count++;
                    }
                }
            }

        }
        System.out.println(count);
        System.out.println(length);
        if (count == length) return true;
        return false;
    }

    private static int getIndex(int x, int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == x) {
                return i;
            }
        }
        return -1;  //若数组中没有则返回-1
    }

    public static boolean canFormArray(int[] arr, int[][] pieces) {

        // 构造 HashMap O(1) 取值
        Map<Integer, int[]> map = new HashMap<>();
        for (int[] piece : pieces) {
            map.put(piece[0], piece);
        }
        // 对单个 piece 数组，遍历对比
        for (int i = 0; i < arr.length; ) {
            int curVal = arr[i];
            if (map.containsKey(curVal)) {
                int[] piece = map.get(curVal);
                for (int value : piece) {
                    if (arr[i] == value) {
                        i++;
                    } else {
                        return false;
                    }
                }
            } else {
                return false;
            }
        }
        return true;
    }

}
